#include <vector>
using namespace std;

class Solution {
public:
    int tribonacci(int n) {
        vector<int> dp(n+1); //开辟n+1个元素空间

        //注意：要考虑越界情况。即当n为0或1时下面代码中的dp[1]=dp[2]=1;就会发生访问越界，因此要单独考虑越界情况
        //n==2时不需要考虑因为dp这种情况是有3个元素空间，允许访问下标2即dp[2]
        if(0 == n)
        return 0;
        if(1 == n)
        return 1;

        dp[0]=0;
        dp[1]=dp[2]=1;
        for(int i = 3;i<=n;++i) //给dp数组赋值
        {
            dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
        }
        return dp[n];
    }
};